package 算法.动态规划;

/**
 * @author Zhu
 * @Description
 * @create 2023-03-10
 */
public class JZ42连续子数组的最大和 {
    //动态规划 O(n) O(n)
    public int FindGreatestSumOfSubArray(int[] array) {
        int[] dp = new int[array.length];
        dp[0] = array[0];
        int maxsum = dp[0];
        for(int i=1; i<array.length; i++){
            dp[i] = Math.max(array[i]+dp[i-1],array[i]);
            maxsum = Math.max(maxsum,dp[i]);
        }
        return  maxsum;
    }

    //动态规划 O(n) O(1)
    public int FindGreatestSumOfSubArray1(int[] array) {
        int x = array[0];
        int y = 0;
        int maxsum = x;
        for(int i = 1; i < array.length; i++){
            //状态转移：连续子数组和最大值
            y = Math.max(x + array[i], array[i]);
            //维护最大值
            maxsum = Math.max(maxsum, y);
            //更新x的状态
            x = y;
        }
        return maxsum;
    }
}
